(A) Field of the Invention
The present invention is related to a Reed Solomon decoder and Inversionless Berlekamp-Massey Algorithm (IBMA) and parallel-to-serial conversion method thereof.
(B) Description of the Related Art
Error correction codes (ECC) are in wide use, with respect to current general applications. For example, consumer electronics using high speed digital communications, optic disc storage and high resolution television all use Reed Solomon decoders.
Nowadays, there are many transmission technologies and equipment that are widely used, and transmission rates have increased from 56 Kbps to several gigabytes per second. However, noise interference may occur during signal transmission, resulting in data receiving errors. Therefore, receiving equipment should be simple, popular and have high efficiency error correction capability to correct transmission errors due to channel noises.
U.S. Pat. No. 6,286,123 B1 disclosed a Berlekamp-Massey Algorithm (BMA) in which a parallel-to-serial interface directly uses multiplexers as interfaces. However, control signals are more complicated and divisional operation devices are needed in BMA architecture.
In U.S. Pat. Nos. 6,317,858 B1 and 6,539,516 B2, although the parallel-to-serial interface of IBMA architecture is changed to be of serial entering, it has less regularity and the error value polynomial is calculated after the error location polynomial is obtained.
A parallel-to-serial interface and an IBMA architecture are compared as follows. FIG. 1 illustrates a traditional Reed Solomon decoder 10 including a syndrome calculator 11, a parallel-to-serial (PS) interface 12, an IBMA apparatus 13, a key equation solver 14, a serial-to-parallel (SP) interface 15, a Chien search device 16 (error location) and a Chien search device 17 (error value), a first-in-first-out (FIFO) circuit 18 and a Forney algorithm device 19. The syndrome calculator 11 receives messages r(x) from a receiving end and calculates syndromes. The syndromes are transmitted to the IBMA apparatus 13 through the parallel-to-serial interface 12. The IBMA apparatus 13 generates an error location polynomial Λ(x) based on the syndromes. The key equation solver 14 generates an error value polynomial Ω(x) based on the syndromes and Λ(x). Λ(x) and Ω(x) are transmitted to the Chien search devices 16 and 17 through the serial-to-parallel interface 15 to solve error locations and the Forney algorithm device 19 calculates error values. r(x) is registered in the FIFO circuit 18 and corrected by the error values obtained by the Forney algorithm device 19, so as to obtain messages c(x) at the end of the transmission.
Accordingly, there are problems with the error value polynomial Ω(x) being obtained after the error location polynomial Λ(x) is obtained, and the parallel-to-serial interface has less regularity.
FIG. 2 illustrates a traditional parallel-to-serial interface using multiplexers. The parallel-to-serial interface includes 16 syndrome cells 22 and a multiplexer 21. The corresponding syndrome sequences are shown in Table 1.
TABLE 1Δ(i)Syndrome sequencesi = 0S1i = 1S2, S1i = 2S3, S2, S1i = 3S4, S3, S2, S1i = 4S5, S4, S3, S2, S1i = 5S6, S5, S4, S3, S2, S1i = 6S7, S6, S5, S4, S3, S2, S1i = 7S8, S7, S6, S5, S4, S3, S2, S1i = 8S9, S8, S7, S6, S5, S4, S3, S2, S1i = 9S10, S9, S8, S7, S6, S5, S4, S3, S2i = 10S11, S10, S9, S8, S7, S6, S5, S4, S3i = 11S12, S11, S10, S9, S8, S7, S6, S5, S4i = 12S13, S12, S11, S10, S9, S8, S7, S6, S5i = 13S14, S13, S12, S11, S10, S9, S8, S7, S6i = 14S15, S14, S13, S12, S11, S10, S9, S8, S7i = 15S16, S15, S14, S13, S12, S11, S10, S9, S8
The IBMA algorithm is a modification from BMA algorithm, with a view to decreasing hardware complexity, in which divisional operation in BMA is replaced with a non-divisional operation and a multiple of the original polynomial is obtained. According to features of Galois Field, the same root can be solved. This algorithm is used for obtaining the error location polynomial Λ(x). The IBMA architecture and calculation are exemplified as follows.
Initial conditions:
D(−1) = 0δ= 1Λ(−1)(x) = 1T(−1)(x) = 1Δ(0) = S1For i=0 to 2t−1{Δ(i+1) = Si+2 * Λ0(i) + Si+1 *Λ1(i) +...+Si−vi+2 *Λvi(i)If Δ(i) =0 or 2D(i−1) ≧ i+1  D(i) = D(i+1)  T(i)(x) = x * T(i−1)(x)  δ = δ  Λ(i)(x) = Λ(i−1)(x)Else  D(i) = i+1−D(i−1)  T(i)(x) = Λ(i−1)(x)  δ = Δ(i)  Λ(i)(x) =δ * Λ(i−1)(x) +δ(i) * x * T(i−1)(x)}Ω(x)mod x2t=S(x)*Λ(2t)(x)                where Λ(i)(x) is the error location polynomial at ith iteration                    Λj(i)(x) is coefficients of orders of Λ(i)(x)                            j is x order                Δ(i) is discrepancy of ith iteration                δ is discrepancy of T(i)(x) with corrected iteration                T(i)(x) is an auxiliary polynomial                D(i) is the highest order of the auxiliary polynomial                S(x) is syndrome array S1˜S2t                 Ω(x) is a key equation                                                
FIG. 3 illustrates a traditional IBMA apparatus 30, and FIG. 4 illustrates the architecture for calculation of a key equation based on the architecture shown in FIG. 3. The IBMA apparatus 30 comprises multipliers 31, 40 and 41, buffers 32 and 37, adders 33 and 39, multiplexers 35 and 43 and registers 34, 36, 38, 42 and 44.
In order to obtain higher regularity and lower hardware complexity, the separated IBMA algorithm can implement serial input data sequences as shown in Table 1. The error location polynomial and the key equation (error value polynomial) after separation are listed in Table 2.
TABLE 2Error location polynomialKey equationΛ(i)(x) = Λ0(i) + Λ1(i)x + . . . + Λvi(i)xvi                              Ω          ⁡                      (            x            )                          =                ⁢                              S            ⁡                          (              x              )                                ⁢                      Λ            ⁡                          (              x              )                                ⁢                                          ⁢          mod          ⁢                                          ⁢                      x                          2              ⁢              t                                                              ≅                ⁢                              Ω                          (              0              )                                +                                    Ω                              (                1                )                                      ⁢            x                    +                      …            ⁢                                                  ⁢                          Ω                              (                                  v                  -                  1                                )                                      ⁢                          x                              v                -                1                                                               Λ    j          (      i      )        =      {                                                      δ              *                              Λ                0                                  (                                      i                    -                    1                                    )                                                      ,                                                j            =            0                                                                                          δ                *                                  Λ                  j                                      (                                          i                      -                      1                                        )                                                              +                                                Δ                                      (                    i                    )                                                  ⁢                                  T                                      j                    -                    1                                                        (                                          i                      -                      1                                        )                                                                        ,                                                1            ≤            j            ≤            vi                              Ω(i) = Si+1Λ0 + SiΛ1 + . . . + S1Λi       Δ          (              i        +        1            )        =            ∑              j        =        0            vi        ⁢                  ⁢          Δ      j              (                  i          +          1                )                  Ω    j          (      i      )        =      {                                                      S                              i                +                1                                      ⁢                          Λ              0                                                                          for              ⁢                                                          ⁢              i                        =            0                                                                          Ω                              j                -                1                                            (                i                )                                      +                                          S                                  i                  -                  j                  +                  1                                            ⁢                              Λ                j                                                                                        for              ⁢                                                          ⁢              1                        ≤            j            ≤            i                                     Δ    j          (              i        +        1            )        =      {                                        0            ,                                                j            =            0                                                                                          Δ                                  j                  -                  1                                                  (                                      i                    +                    1                                    )                                            +                                                S                                      i                    -                    j                    +                    3                                                  *                                  Λ                                      j                    -                    1                                                        (                    i                    )                                                                        ,                                                1            ≤            j            ≤            vi                              
As shown in Table 2, the error value polynomial Ω(x) is derived based on the error location polynomial Λ(x). In other words, Λ(x) is obtained first so as to obtain Ω(x). Moreover, as mentioned above, the parallel-to-serial interface has less regularity, so there still remains room for improvement.